package main

import "fmt"

const (
	// 行
	RAW int = 5
	// 列
	COL int = 6
)

// 物品的重量 舍弃数组的0位置元素
var weight = [RAW]int{0, 1, 4, 2, 1}

// 物品的价值 舍弃数组的0位置元素
var value = [RAW]int{0, 1500, 3000, 2000, 300}

// 动态规划网格
var cells [RAW][COL]int

// 用于回溯选择的商品 selected[i]=1 表示放进背包，0表示不放进背包
var selected [RAW]int

// 动态规划计算网格
func dynamic() {

	for i := 1; i < len(value); i++ {
		for j := 1; j < 6; j++ {
			cells[i][j] = maxValue(i, j)
		}
	}
	for i := 0; i < RAW; i++ {
		fmt.Printf("raw is %v \n", cells[i])
	}
	findBack()
	fmt.Printf("selected goods is %v \n", selected)
}

// 判断当前单元格最大价值方法
func maxValue(i, j int) int {
	// 当前商品无法放入背包，返回当前背包所能容纳的最大价值
	if j < weight[i] {
		return cells[i-1][j]
	}
	// 可放进背包时候，计算放入当前商品后的最大价值
	curr := value[i] + cells[i-1][j-weight[i]]
	// 与当前商品不放进背包的最大价值比较，看是否应该放进背包
	if curr >= cells[i-1][j] {
		return curr
	}
	return cells[i-1][j]
}

// 回溯选择的商品方法
func findBack() {
	col := COL - 1
	for i := RAW - 1; i > 0; i-- {
		if cells[i][col] > cells[i-1][col] {
			selected[i] = 1
			col = col - weight[i]
		} else {
			selected[i] = 0
		}
	}
}

func main() {
	dynamic()
}
